Field of the Invention
The invention relates to a method of assigning electrical connections to the several layers of a multilayer interconnection package to effect a distribution of the electrical connections. More particularly, the invention relates to a method for distributing electrical connections among the layers of a multilayer interconnection package, in such a manner that the number of connections passing through each region of the package is evenly balanced among all the layers, and such that each connection or each net, comprising one or more connections, is assigned to a single layer.
Description of the Prior Art
In order to facilitate the understanding of the present invention and the prior art the following background information is provided.
The electrical connection of individual components on large or very large scale integrated circuits and interconnection packages is achieved using metallic paths between the endpoints (or pins) which are to be connected. A path between two pins is referred to as a connection. A net is a specified set of one or more connections. Generally, the connections of a net are all electrically in common; that is, there is a path joining any two pins of the net, either directly or by means of other pins of the net. The method of the present invention does not, however, require this property of electrical commonality.
The present invention is concerned with packages that contain more than one wiring layer and that are designed so that each connection is required to be routed completely within one of the layers. That is, the path for a connection passes from one pin, down to a wiring layer, then to a point beneath the other pin, still within the same wiring layer, then to the other pin. A layer typically, but not necessarily, comprises a pair of wiring planes, often referred to as `x` and `y` planes when the predominant direction of wiring within each plane of the layer is disposed along orthogonal `x` and `y` axes respectively.
In designing a multilayer interconnection package, it is necessary to specify the layer in which each connection is to be routed. The present invention provides a method that assigns each connection to a layer in such a way that wire load in each region (number and length of connections passing through the region) is evenly balanced among the layers of the package. (`Region` means a portion of the package that comprises all layers, but is limited in areal extent in the x-y plane.)
It may also be necessary or desirable to assign complete nets to layers; that is, to assign connections to layers in such a way that, for every net, all connections of the same net are assigned to the same layer. The present invention also provides a method for making such an assignment while providing evenly balanced wire load in each region of the package.
There are several reasons why assignment of complete nets to layers may be necessary or desirable. First, certain package technologies require or benefit from this constrained assignment for electrical or fabrication reasons. Second, such assignment can allow the subsequent wire routing to be done independently for each layer, even though the routing process for a connection may depend upon knowledge of the positions or routings of other connections of the same net. For example, the electrical properties of the package may have to be controlled for each net, and the routed lengths of other connections of a net may need to be known before a given connection can be routed. Third, rework or repair of the package can be facilitated if all connections of a net are wired within the same layer.
Now with respect to the prior art, several methods exist for assigning connections to layers in a multilayer package. One method is to use a sequential routing procedure. In such a method, one attempts to route a connection in a first layer without violating package design rules. If this fails, one attempts to route the connection in a second layer, etc. until a valid routing is found or the connection fails to be routed. One then proceeds to the next required connection. This can result in an imbalance between the number (and total length) of connection paths on the several layers, which can lead to a requirement for more wiring layers than would be the case according to the method of the present invention.
A second method is to randomly assign each connection to some layer, so that each connection has an equal probability of being assigned to any of the layers. This method results in regional inbalances of wire load among the layers, due to statistical fluctuations. To understand this, suppose that a total of N wires traverse a region, and that there are L layers. The average number of wires traversing the region in each layer is N/L, but the actual number of wires in each layer will deviate from N/L by a number on the order of the square root of (N/L), because of statistical fluctuations. The same result applies if we denote by N the number of wires connecting pins that lie in two specified regions. In contrast, as will be seen, the present invention distributes connections among layers in such a way that the number of connections between pins that lie in two specified regions is evenly balanced among the layers, without such statistical fluctuations.
Another method for assigning connections to layers is disclosed in a commonly-assigned, copending patent application, U.S. Ser. No. 562,754, now U.S. Pat. No. 4,615,011, issued Sept. 30, 1986, entitled: "Iterative Method for Establishing Connections and Resulting Product," by R. Linsker. The aspect of that invention that relates to assignment of connections to layers, comprises a method of initially randomly assigning to each connection a layer and an initial approximate wire routing (referred to as a global routing), then iteratively removing and rerouting each connection in turn so as to determine a new routing (and layer assignment) that minimizes certain undesirable routing characteristics at each iterative step.
Another wiring method is described by S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, in a paper entitled: "Optimization by Simulated Annealing," Science, Vol. 220, pages 671-680, May 13, 1983; and in a paper by M. P. Vecchi and S. Kirkpatrick entitled: "Global Wiring by Simulated Annealing," IEEE Transactions on ComputerAided Design, Vol. CAD-2, No. 4, pages 215-222, October 1983. The method described therein is limited to routing using "L" and "Z" wire path shapes. It considers at each step of the routing procedure only one possible alternative wire path for a connection, and evaluates a specific penalty function equal to the sum of the squares of the numbers of wires crossing each edge of the global cell.
In contrast to the methods described above, the method of the present invention does not require that a wire routing be performed in order to determine layer assignments. Furthermore, the present invention can be used to assign connections to layers with resulting balanced wire load in each region of the package, even when all connections of each net are required to be assigned to the same layer.
Also noted is a commonly-assigned, patent application, U.S. Ser. No. 317,651, entitled: "Optimization of an Organization of Many Discrete Elements," now U.S. Pat. No. 4,495,559 issued Jan. 22, 1985, by C. D. Gelatt, Jr. and E. S. Kirkpatrick. In the method of that application, elements are initially assigned to locations, then a sequence of possible moves are considered in turn. For each move, a score is computed, and the move is made if the score for that move is negative. If the score is positive, the move is made with probability equal to the exponential of minus the ratio of the score to a number T. The value of T is first increased, then decreased gradually as the process continues. An aspect of the present invention relates to the making of a decision on a probabilistic basis, for the case in which all connections of each net must be assigned to the same layer. While this decision can be made using a random number and a T-value that decreases gradually during the process, this is not required. Even when the decision is made in this way, a plurality of possible moves are considered simultaneously, and the decision to make or not to make any of the moves is made on a different basis than in the prior art method. Furthermore, the present invention relates to connection or net assignment, and teaches the use of `connection type` classes as a means for balancing wire load among layers; the prior art method does not relate to these issues.